//
// Created by wdq on 2022/9/15.
//
#include <iostream>
#include <cstring>
#include <set>

using namespace std;

struct ArcNode {
    char data;
    int adjvex;
    int info;
    ArcNode *nextarc;

    ArcNode(int adjvex, int info, char data) {
        this->data = data;
        this->adjvex = adjvex;
        this->info = info;
        this->nextarc = nullptr;
    }

    void output() const {
        cout << "->" << data << endl;
    }
};

struct VexNode {
    char data{};
    ArcNode *firstarc;

    VexNode() {
        this->firstarc = nullptr;
    }

    void addArc(int adjvex, int info, char vexData) {
        auto *p = new ArcNode(adjvex, info, vexData);
        p->nextarc = firstarc;
        firstarc = p;
    }

    void output() const {
        ArcNode *p = firstarc;
        while (p) {
            cout << data;
            p->output();
            p = p->nextarc;
        }
    }
};

struct ALGraph {
    VexNode *vertices;
    int edgeNum;
    bool isDirected;

    explicit ALGraph(const char *names, bool isDirected = true) {
        int length = int(strlen(names));
        this->edgeNum = length;
        this->isDirected = isDirected;
        this->vertices = new VexNode[edgeNum];
        for (int i = 0; i < length; i++) {
            this->vertices[i].data = names[i];

        }
    }

    void addArc(int head, int tail, int weight = 0) const {
        if (!isDirected) {
            vertices[tail].addArc(head, weight, vertices[head].data);
        }
        vertices[head].addArc(tail, weight, vertices[tail].data);

    }

    void output() const {
        for (int i = 0; i < edgeNum; i++) {
            vertices[i].output();
        }
    }
};

void prim(ALGraph &G) {
    set<VexNode *> choose;
    set<VexNode *> noChoose;

    choose.insert(&G.vertices[0]);
    for (int i = 1; i < G.edgeNum; i++) {
        noChoose.emplace(&G.vertices[i]);
    }
    while (int(choose.size()) != G.edgeNum) {
        VexNode *start = nullptr;
        int point = -1;
        int minWeight = INT32_MAX;
        for (auto &node: choose) {
            auto temp = node->firstarc;
            while (temp) {
                if (noChoose.count(&G.vertices[temp->adjvex]) && temp->info < minWeight) {
                    minWeight = temp->info;
                    point = temp->adjvex;
                    start = node;
                }
                temp = temp->nextarc;
            }
        }
        cout << start->data << " -> " << G.vertices[point].data << " : " << minWeight;
        cout << endl;
        noChoose.erase(&G.vertices[point]);
        choose.emplace(&G.vertices[point]);

    }


}

int main() {
    const char *p = "abcdef";
    ALGraph g(p, false);
    g.addArc(0, 1, 6);
    g.addArc(0, 3, 5);
    g.addArc(0, 2, 1);
    g.addArc(1, 2, 5);
    g.addArc(1, 4, 3);
    g.addArc(2, 4, 6);
    g.addArc(2, 3, 5);
    g.addArc(2, 5, 4);
    g.addArc(3, 5, 2);
    g.addArc(4, 5, 6);
//    g.output();
    cout << "prim: " << endl;
    prim(g);


    return 0;
}